iT邦幫忙

2024 iThome 鐵人賽

DAY 6
0

🟨最長回文字子序列(解法1)

題目

本題取自 Leetcode 516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".


Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".
 

Constraints:

1 <= s.length <= 1000
s consists only of lowercase English letters.

分析

本題要尋找給定字串當中最長的回文字子序列長度。

回文字指的是正著讀、倒著讀都一樣的文字(字數不限奇數偶數,因此abbaabaaaa都是回文字)

和day9遇到過的子字串定義不太相同,子序列可以由給定字串(或者陣列)當中取出任意的片段並重新串接,但順序要維持不變。例如'abcd'的子序列包含'abd',但不包含'ca'(因為字母順序和原字串不同)。


那麼要如何找出題目所要求的「最長的回文字子序列」呢?

暴力破解(brute force)顯然是不現實的,因為每一個字母都可以取或者不取,光是暴力枚舉(enumerate)出所有的子序列就需要O(2^n)指數時間,顯然必須尋找不同的途徑。

對於這種找最大/最小值,且暴力解明顯不通的時候,可以試著從「貪心一點」的角度來重構問題:

若一個字串是回文字,則最首字母和最尾字母必定相同。換言之:若一個字串的最首字母和最尾字母不同,則必定不為回文字

因為「子序列」必須從原字串中切出,且字母順序必須維持不變,若一個字串的最首字母和最尾字母不同,則這個字串本身必定不符合「回文字子序列」的要求。既然如此,就必須至少捨棄掉字首或者字尾其中之一。

反過來說,若最首字母和最尾字母相同,則此字首/字尾必定包含於最長回文子序列當中

分治法

舉例來說,給定一個字串'lilya',先檢查頭尾是否相同,發現首尾不同,代表字首的'l'與字尾的'y'不可能同時存在於所求答案的「最長回文字子序列」當中。

因此,答案必定在「掐頭或者去尾」,也就是'ilya''lily'當中其中一個。

若首尾相同,則所求答案的「最長回文字子序列」必定包含這兩個字母,可以直接扣除這兩個字母繼續比對。

例如給定一個字串'tenet',由於首尾字母相同,答案的「最長回文字子序列」必定包含't...t',因此繼續比對中間的'ene'

設計狀態、找出轉移式與最小問題

狀態:以lenLPS(i,j)代表給定字串s的子字串s[i:j+1]當中的最長回文子序列長度

轉移式

i>j:空字串(邊界條件),lenLPS(i,j) = 0

i==j:剩一個字母(最小子問題),lenLPS(i,j) = 1

s[i] == s[j]lenLPS(i,j) = 2 + lenLPS(i+1, j-1)

s[i] != s[j]lenLPS(i,j) = max( lenLPS(i+1, j), lenLPS(i,j-1) )

母問題lenLPS(0,len(s)-1)

以字串字串'lilya'為例,遞迴求解的過程如下圖:

alt text

實作

Top-Down DP

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @cache
        def lenLPS(i,j):
            if i>j: 
                return 0
            if i==j: 
                return 1
            if s[i]==s[j]: 
                return 2 + lenLPS(i+1,j-1)
            return max(lenLPS(i+1,j), lenLPS(i,j-1))
        return lenLPS(0, len(s)-1)

Bottom-Up DP

前述的遞迴邏輯,在設計Bottom-Up時計算順序該如何規劃呢?

參考'lilya'的例圖,發現要從圖中的由下往上計算(因為上面的子問題會用到下面的子問題答案)。而並不是由特定的index順序開始計算,而是在s的子字串中從短到長的順序計算。

因此,和前述Top-Down的狀態稍有不同

我們定義狀態l來代表所檢查子字串的長度,並且以狀態i來代表該子字串的起始位置。

並且用dp[l,i]記錄s[i:i+l]子字串本身所包含的最長回文子序列長度

因此,最小問題dp[0]全為0(因為代表空字串),dp[1]全為1(因為長度為1的子字串必為回文字)。

之所以需要dp[0],是因為當計算dp[2]時若是回文字,轉移式會需要用到dp[0],為了避免index overflow,同時也不想要在轉移式中多加一個條件判斷,就和前幾天的矩陣題一樣,採用這個增加一列邊界值的做法。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0]*n,[1]*n]
        for l in range(2, n+1):
            dp.append([
                2+dp[-2][i+1] if s[i]==s[i+l-1] else max(dp[-1][i:i+2]) 
                for i in range(0,n-l+1)])
        return dp[-1]

如果還是看不太懂,可以將上例的dp逐行印出,能看出就是前述'lilya'例圖中,子問題答案的反序:

[0, 0, 0, 0, 0]
[1, 1, 1, 1, 1]
[1, 1, 1, 1]
[3, 1, 1]
[3, 1]
[3]

本例一樣可以改寫為Rolling的形式來節省空間,由於轉移式會用到dp[-2],代表需要保留最後兩列的狀態。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        pre = [0]*n
        cur = [1]*n
        for l in range(2, n+1):
            pre, cur = cur, [
                2+pre[i+1] if s[i]==s[i+l-1] else max(cur[i:i+2]) 
                for i in range(0,n-l+1)]
        return cur[0]

複雜度分析

時間複雜度

時間複雜度 = 狀態轉移數 x 計算複雜度

本題的狀態數 = O(n^2)n = len(s)

計算複雜度為O(1)

因此總時間複雜度 = O(n^2)

空間複雜度

空間複雜度 = 狀態數 = O(n^2)

若採用Rolling Bottom Up DP的技巧,則降低一個維度,空間複雜度 = O(n)


🟨最長回文字子序列(解法2)

分析

除了前述的解題邏輯,若你對昨天的最長共同子序列(LCS)題型印象深刻,本題還可以重述如下:

求給定字串s以及其反序字串ss = s[::-1]的最長共同子序列(LCS)長度。

alt text

圖上的紅色線,表示sss之間的LCS的對應關係,而綠色線則代表原本題目所求,字串s本身的LPS。可以發現,兩者就是一樣的。

實作

可以直接拿昨天的LCS來用,只需要把text1text2分別代入ss[::-1]即可

因為原本就是同一個字串,只是反序,所以不存在「兩個字串不共用」的字母,因此和昨天的題目不同,這部分的優化可以不做(做了也沒有效果)。


結語

LPS也是我很喜歡的題型。兩種思維、兩個不同的狀態設計與轉移式,竟然能夠殊途同歸並且有相同的時間、空間複雜度。特別是第二種解法,利用了回文字本身的特殊性質,相當有巧思。


以上為Day12的內容!感謝你的閱讀,如果有不同的想法或心得,歡迎留言一同討論!

本文也同步登載在我的個人部落格,記錄我的學習筆記與生活點滴,歡迎來逛逛。

明天會繼續看字串題型的例題。


上一篇
Day 11 字串題型(三) 最長的共同子序列(LCS)
下一篇
Day 13 字串題型(五) 編輯距離
系列文
刷題小白與Python的動態規劃之旅13
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言